package lanqiao.真题.第13届Java大学B组;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 已知一个长度为N的数组：A1,A2,A3,AN恰好是1~N的一个排列。
 * 现在要求你将A数组切分成若干个（最少一个，最多N个）连续的子数组，
 * 并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
 * <p>
 * 例如对于A={1,3,2,4},一共有5种切分方法：
 * {1}{3}{2}{4}:每个单独的数显然是（长度为1的）一段连续的自然数。
 * {1}{3,2}{4}:{3,2}包含2到3，是一段连续的自然数，另外{1}和{4}显然
 * 也是。
 * {1}{3,2,4}：{3,2,4}包含2到4，是一段连续的自然数，另外{1}显然也是。
 * {1,3,2}{4}: {1,3,2}包含1到3，是一段连续的自然数，另外{4}显然也是。
 * {1,3,2,4}:只有一个子数组，包含1到4，是一段连续的自然数。
 * <p>
 * <p>
 * 【输入格式】
 * 第一行包含一个整数N。第二行包含N个整数，代表A数组。
 * 【输出格式】
 * 输出一个整数表示答案。由于答案可能很大，所以输出其对1000000007取
 * 模后的值
 * 【样例输入】
 * 4
 * 1	3	2	4
 * <p>
 * 【样例输出】
 * 5
 * <p>
 * 【评测用例规模与约定】
 * 对于30%评测用例，1≤N≤20.
 * 对于100%评测用例，1≤N≤10000.
 * @since 2023 - 03 - 11 - 9:23
 */
public class G_数组切分 {
}

//dp
class Main_G_1 {
    /*
    1.判断连续：一段子数组在包含一段连续的自然数时: 区间 max − min = R − L
    2.动态转移方程：当区间[j, i]是一段连续自然数时,f[i] = (f[i] + f[j - 1])
    3.初始化时应该置f[0]=1
    整体时间复杂度：O(n^2)
     */
    static int mod = (int) 1e9 + 7;
    static int n;
    static int[] arr;
    static long[] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n + 1];
        dp = new long[n + 1];
        for (int i = 1; i <= n; ++i) {
            arr[i] = sc.nextInt();
        }
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            // 记录 j - i 区间，最大值和最小值
            int max = arr[i], min = arr[i];
            for (int j = i; j >= 1; j--) {
                max = Math.max(max, arr[j]);
                min = Math.min(min, arr[j]);
                //j - i 区间是 连续的情况
                if (max - min == i - j) {
                    //j位置可以切一刀， 多了dp[j - 1]种
                    dp[i] = (dp[i] + dp[j - 1]) % mod;
                }
            }
        }

        System.out.println(dp[n]);
    }
}

//dfs
class Main_G {
    static boolean[] vis;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] arr = new int[N];
        vis = new boolean[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scanner.nextInt();
        }
        long ans = DFS(arr, 0);
        System.out.println(ans);
    }

    private static long DFS(int[] arr, int k) {
        if (k == arr.length - 1) {
            if (check(arr)) {
//				for(int i=0;i<vis.length;i++) {
//					System.out.print(vis[i] + " ");
//				}
//				System.out.println();
                return 1;
            }
            return 0;
        }
        // 当前位置切
        int res = 0;
        vis[k] = true;
        res += DFS(arr, k + 1);
        vis[k] = false;

        // 当前位置不切
        res += DFS(arr, k + 1);
        return res;
    }

    private static boolean check(int[] arr) {
        // TODO 检查当前切法是否符合规则
        int len = arr.length;
        int p = 0;
        int q = 1;
        while (q < len) {
            if (vis[q - 1]) {
                if (!check_lianxu(arr, p, q)) {
                    return false;
                }
                p = q;
            }
            q++;
        }
        return check_lianxu(arr, p, q);
    }

    private static boolean check_lianxu(int[] arr, int p, int q) {
        // TODO 检测数组是否连续p-q
        int[] arrCopy = new int[q - p];
        System.arraycopy(arr, p, arrCopy, 0, q - p);
        Arrays.sort(arrCopy);
        for (int i = 0; i < q - p - 1; i++) {
            if (arrCopy[i + 1] - arrCopy[i] != 1) {
                return false;
            }
        }
        return true;
    }
}
